package com.demo.链表.chenglei;

import cn.hutool.core.lang.Console;

import java.util.*;

/**
 * @author cl
 */
public class Linked {
    public static void main(String[] args) {
        Integer[] singleLinked = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        LinkedNode<Integer> linked1 = makeSingleLinked(singleLinked, true);
        printSingleLinked(linked1);

        // 链表逆转
        // 1. 迭代的方式逆转链表
        Console.log("迭代的方式逆转链表");
        printSingleLinked(迭代反转链表(makeSingleLinked(singleLinked, true)));
        // 2 迭代的方式逆转链表
        Console.log("递归反转链表");
        printSingleLinked(递归反转链表(makeSingleLinked(singleLinked, true)));
        // 3 头插法反转链表
        Console.log("头插法反转链表");
        printSingleLinked(头插法反转链表(makeSingleLinked(singleLinked, true)));
        // 3 就地逆置法反转链表
        Console.log("就地逆置法反转链表");
        printSingleLinked(就地逆置法反转链表(makeSingleLinked(singleLinked, true)));
        快慢指针找位置();
        两个有序链表的共通组成();
        回文链表证明();
        链表排序();
        复制含有随机指针的链表();
    }

    private static void 复制含有随机指针的链表() {
        // 借助 map 进行复制


    }

    private static void 链表排序() {
        Integer[] test0 = new Integer[]{8, 45, 1, 23, 3, 8, 7, 9, 8, 44, 0};
        LinkedNode<Integer> head0 = makeSingleLinked(test0, true);
        Console.log("对链表进行排序，小于8在左边，等于在中间，大于在右边: {}", Arrays.toString(test0));
        LinkedNode minHead, minTail, midHead, midTail, maxHead, maxTail;
        minHead = minTail = midHead = midTail = maxHead = maxTail = null;
        while (head0 != null && head0.next != null) {
            if (head0.data == 8) {
                if (null == midHead) {
                    midHead = head0;
                    midTail = head0;
                } else {
                    midTail.next = head0;
                    midTail = midTail.next;
                }
            } else if (head0.data < 8) {
                if (null == minHead) {
                    minHead = head0;
                    minTail = head0;
                } else {
                    minTail.next = head0;
                    minTail = minTail.next;
                }
            } else {
                if (null == maxHead) {
                    maxHead = head0;
                    maxTail = head0;
                } else {
                    maxTail.next = head0;
                    maxTail = maxTail.next;
                }
            }
            head0 = head0.next;
        }
        minTail.next = midHead;
        midTail.next = maxHead;
        Console.log("排序结果为: ", Arrays.toString(getListByLinked(minHead).toArray()));
    }

    private static void 回文链表证明() {
        Integer[] test0 = new Integer[]{2, 2};
        Integer[] test1 = new Integer[]{1, 2, 3, 4, 4, 3, 2, 1};
        Integer[] test2 = new Integer[]{1, 2, 3, 5, 3, 2, 1};
        Integer[] test3 = new Integer[]{1, 2, 3, 5, 5, 2, 1};
        LinkedNode<Integer> head0 = makeSingleLinked(test0, true);
        LinkedNode<Integer> head1 = makeSingleLinked(test1, true);
        LinkedNode<Integer> head2 = makeSingleLinked(test2, true);
        LinkedNode<Integer> head3 = makeSingleLinked(test3, true);
        Console.log("使用栈证明回文链表 0: {}, 结果: {}", Arrays.toString(test0), 使用栈证明回文链表(head0));
        Console.log("使用栈证明回文链表 1: {}, 结果: {}", Arrays.toString(test1), 使用栈证明回文链表(head1));
        Console.log("使用栈证明回文链表 2: {}, 结果: {}", Arrays.toString(test2), 使用栈证明回文链表(head2));
        Console.log("使用栈证明回文链表 3: {}, 结果: {}", Arrays.toString(test3), 使用栈证明回文链表(head3));
        Console.log("快慢指针证明回文链表 0: {}, 结果: {}", Arrays.toString(test0), 快慢指针证明回文链表(head0));
        Console.log("快慢指针证明回文链表 1: {}, 结果: {}", Arrays.toString(test1), 快慢指针证明回文链表(head1));
        Console.log("快慢指针证明回文链表 2: {}, 结果: {}", Arrays.toString(test2), 快慢指针证明回文链表(head2));
        Console.log("快慢指针证明回文链表 3: {}, 结果: {}", Arrays.toString(test3), 快慢指针证明回文链表(head3));
    }

    private static boolean 使用栈证明回文链表(LinkedNode<Integer> head) {
        Stack<LinkedNode> stack = new Stack<>();
        LinkedNode tmp = head;
        while (tmp != null && tmp.next != null) {
            stack.push(tmp);
            tmp = tmp.next;
        }
        if (tmp != null) {
            stack.push(tmp);
        }
        int size = stack.size();
        for (int i = 0; i < (size >> 1); i ++) {
            if (head.data != stack.pop().data) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    private static boolean 快慢指针证明回文链表(LinkedNode<Integer> head) {
        LinkedNode slowPoint = head;
        LinkedNode quickPoint = head;
        // 快慢指针 居左
        while (slowPoint != null && slowPoint.next != null && quickPoint.next != null && quickPoint.next.next != null) {
            slowPoint = slowPoint.next;
            quickPoint = quickPoint.next.next;
        }
        if (slowPoint == null) {
            return false;
        }
        // 目前的 slowPoint 指向左终点 将后面的部分翻转
        // 使用原地逆转的方法
        LinkedNode s = slowPoint;
        LinkedNode currentNode = slowPoint.next;
        while (Objects.nonNull(currentNode)) {
            s.next = currentNode.next;
            currentNode.next = slowPoint;
            slowPoint = currentNode;
            currentNode = s.next;
        }
        while (slowPoint.next != null) {
            if (head.data != slowPoint.data) {
                return false;
            }
            head = head.next;
            slowPoint = slowPoint.next;
        }
        return true;
    }

    private static void 两个有序链表的共通组成() {
        Console.log("两个从小到大的链表的共通组成---");
        Integer[] test0 = new Integer[]{0, 2, 7, 9, 12, 14, 32, 56};
        Integer[] test1 = new Integer[]{1, 5, 7, 12, 14, 56, 77};
        LinkedNode<Integer> head0 = makeSingleLinked(test0, true);
        LinkedNode<Integer> head1 = makeSingleLinked(test1, true);
        Console.log("有序链表0: {}", Arrays.toString(test0));
        Console.log("有序链表1: {}", Arrays.toString(test1));

        LinkedList tmp = new LinkedList();
        // 谁小 谁前进
        while (head0 !=null && head1 != null) {
            if (head0.data < head1.data) {
                head0 = head0.next;
            } else if (head0.data > head1.data) {
                head1 = head1.next;
            } else {
                tmp.add(head0.data);
                head0 = head0.next;
                head1 = head1.next;
            }
        }
        Console.log("两个从小到大的链表的共通组成: {}", Arrays.toString(tmp.toArray()));
    }

    private static void 快慢指针找位置() {
        Console.log("快慢指针找位置:");
        Integer[] test0 = new Integer[]{};
        Integer[] test1 = new Integer[]{1};
        Integer[] test2 = new Integer[]{1, 2};
        Integer[] test3 = new Integer[]{1, 2, 3};
        Integer[] test4 = new Integer[]{1, 2, 3, 4};
        Integer[] test5 = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        Integer[] test6 = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        Console.log("快慢指针，为空时不进行，1个数时不进行，2个数时根据取左，取右？ 默认取左");
        快慢指针(test0);
        快慢指针(test1);
        快慢指针(test2);
        快慢指针(test3);
        快慢指针(test4);
        快慢指针(test5);
        快慢指针(test6);
    }

    private static void 快慢指针(Integer[] test) {
        LinkedNode head = makeSingleLinked(test, true);
        LinkedNode slowPoint = head;
        LinkedNode quickPoint = head;
        // head.next == null 那么就是一个节点
        // 下面的条件只有节点数是基数 且大于等于3 才成立
        while (slowPoint != null && slowPoint.next != null && quickPoint.next != null && quickPoint.next.next != null) {
            slowPoint = slowPoint.next;
            quickPoint = quickPoint.next.next;
        }

        Console.log("快慢指针，中点的值为:{}, 右取值：{}", slowPoint != null ? slowPoint.data: null, (slowPoint != null && slowPoint.next != null) ? slowPoint.next.data : null);
    }

    private static LinkedNode 就地逆置法反转链表(LinkedNode<Integer> head) {
        if (Objects.isNull(head) || Objects.isNull(head.next)) {
            return head;
        }
        LinkedNode s = head;
        LinkedNode n = head.next;
        while (Objects.nonNull(n)) {
            s.next = n.next;
            n.next = head;
            head = n;
            n = s.next;
        }
        return head;
    }

    private static LinkedNode 头插法反转链表(LinkedNode<Integer> head) {
        if (Objects.isNull(head) || Objects.isNull(head.next)) {
            return head;
        }
        LinkedNode newHead = null;
        LinkedNode tmp = null;
        while (Objects.nonNull(head)) {
            // 弹一个元素
            tmp = head;
            // 下一个元素
            head = head.next;
            // 头插法
            tmp.next = newHead;
            newHead = tmp;
        }
        return newHead;
    }

    private static LinkedNode 迭代反转链表(LinkedNode<Integer> head) {
        if (Objects.isNull(head) || Objects.isNull(head.next)) {
            return head;
        }
        LinkedNode s = null;
        LinkedNode c = head;
        LinkedNode e = head.next;
        while (Objects.nonNull(e)) {
            c.next = s;
            s = c;
            c = e;
            e = e.next;
        }
        c.next = s;
        return c;
    }

    private static LinkedNode 递归反转链表(LinkedNode<Integer> head) {
        if (Objects.isNull(head) || Objects.isNull(head.next)) {
            return head;
        }
        LinkedNode tmp = 递归反转链表(head.next);
        head.next.next = head;
        head.next = null;
        return tmp;
    }

    /** 根据数组 做成一个单链表 */
    public static <T> LinkedNode<T> makeSingleLinked(T[] t, boolean headHaveValue) {
        if (t.length == 0) {
            return null;
        }
        LinkedNode<T> head = new LinkedNode<>();
        LinkedNode current = head;
        for (T d : t) {
            LinkedNode<T> node = new LinkedNode<>();
            node.data = d;
            current.next = node;
            current = current.next;
        }
        return headHaveValue ? head.next : head;
    }

    /** 做成一个环链表 */
    public static <T> List<Linked.LinkedNode<T>> createCircleLinked(T[] t, T c) {
        Linked.LinkedNode<T> head = Linked.makeSingleLinked(t, true);
        Linked.LinkedNode<T> circleNode = Linked.getLinkedNode(head, c).get(0);
        Linked.LinkedNode<T> tailNode = head;
        while (tailNode.next != null && (tailNode = tailNode.next) != null){}
        tailNode.next = circleNode;
        return new ArrayList<Linked.LinkedNode<T>>(){{add(head); add(circleNode);}};
    }

    /** 打印一个单链表 */
    public static void printSingleLinked(LinkedNode head) {
        Objects.requireNonNull(head);
        Console.log("Head [{}]", head.data);
        while (head.next != null) {
            Console.log("   ↓   ");
            Console.log("  [{}]  ", head.next.data);
            head = head.next;
        }
    }

    /** 打印一个单链表 */
    public static String printSingleLinkedToString(LinkedNode head) {
        StringBuilder stringBuilder = new StringBuilder("链表: [ ");
        while (head != null) {
            stringBuilder.append(head.data);
            head = head.next;
            if (head != null) {
                stringBuilder.append(" -> ");
            }
        }
        stringBuilder.append(" ]");
        return stringBuilder.toString();
    }

    /** 打印一个环链表 */
    public static String printSingleLinkedToString(LinkedNode head, LinkedNode circle) {
        StringBuilder stringBuilder = new StringBuilder("环链表: [ ");
        boolean c = false;
        while (head != null) {
            if (head == circle) {
                stringBuilder.append("环点");
                if (c) {
                    break;
                } else {
                    c = !c;
                }
            }
            stringBuilder.append(head.data);
            head = head.next;
            if (head != null) {
                stringBuilder.append(" -> ");
            }
        }
        stringBuilder.append(" ]");
        return stringBuilder.toString();
    }

    /** 链表转list */
    public static <T> List<T> getListByLinked(LinkedNode<T> head) {
        Objects.requireNonNull(head);
        List<T> list = new ArrayList<>();
        while (head.next != null) {
            list.add(head.data);
            head = head.next;
        }
        return list;
    }

    // 寻找指定数据的节点
    public static <T> List<LinkedNode<T>> getLinkedNode(LinkedNode<T> head, T t) {
        List<LinkedNode<T>> tmp = new ArrayList<>();
        while (head != null) {
            if (head.data == t) {
                tmp.add(head);
            }
            head = head.next;
        }
        return tmp;
    }

    public static class LinkedNode<T> {
        /** 下一个节点 */
        public LinkedNode next;
        /** 前一个节点 */
        public LinkedNode provide;
        /** 节点元素 */
        public T data;

        public LinkedNode() {}
        public LinkedNode(T data) { this.data = data;}
    }
}